
#include <iostream>
#include <string>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

using namespace std;

template<class T>
class Stack
{
public:
    
    Stack(int capacity = 4)
        :_a(nullptr)
         ,_top(0)
         ,_capacity(capacity)
    {
        if (_capacity > 0)
        {
            _a = new T[capacity];
        }
    }

    Stack(const Stack& st)
        :_a(nullptr)
         ,_top(st._top)
         ,_capacity(st._capacity)
    {
        if (_capacity > 0)
        {
            _a = new T[_capacity];
            memcpy(_a, st._a, sizeof(T) * st._top);
        }
    }

    ~Stack()
    {
        delete[] _a;
        _top = _capacity = 0;
    }

    void Push(T x)
    {
        if (_top == _capacity)
        {
            int newcapacity = _capacity == 0 ? 4 : _capacity * 2;
            T* tmp = new T[newcapacity];

            if (_a)
            {
                memcpy(tmp, _a, sizeof(T) * _top);
                delete[] _a;
            }

            _a = tmp;
            _capacity = newcapacity;
        }

        _a[_top ++ ] = x;
    }

    Stack& operator=(const Stack& st)
    {
        T* tmp = new T[st._capacity];
        memcpy(tmp, st._a, sizeof(T) * st._top);
        delete[] _a;
        _a = tmp;
        _capacity = st._capacity;
        _top = st._top;

        return *this;
    }

    void Pop()
    {
        assert(!Empty());

        _top -- ;
    }

    bool Empty() const
    {
        return _top == 0;
    }

    T Top()
    {
        assert(!Empty());

        return _a[_top - 1];
    }

private:

    T* _a;
    int _top;
    int _capacity;
};

